package Leetcode.树;

/**
 * @ClassName 二叉树中的最长交错路径
 * @since: 2023/8/19 11:10
 * @auth: kirito
 * @description:
 * 给你一棵以 root 为根的二叉树，二叉树中的交错路径定义如下：
 *
 * 选择二叉树中 任意 节点和一个方向（左或者右）。
 * 如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。
 * 改变前进方向：左变右或者右变左。
 * 重复第二步和第三步，直到你在树中无法继续移动。
 * 交错路径的长度定义为：访问过的节点数目 - 1（单个节点的路径长度为 0 ）。
 *
 * 请你返回给定树中最长 交错路径 的长度。
 *
 * 函数longestZigZag是入口函数，通过调用visit函数从根节点开始访问，并将初始的左子树最大长度和右子树最大长度都设为0。最后返回最长的zigzag路径长度。
 *
 * 在visit函数中，首先更新最大长度max，
 * 取左子树最大长度leftMax和右子树最大长度rightMax的较大值。
 * 然后判断当前节点是否为空，如果为空，则结束访问。接着访问左子树，
 * 如果左子树存在，以当前节点作为右拐点，继续向右子树方向访问，
 * 即visit(root.left, rightMax + 1, 0)，左子树最大长度加1，
 * 右子树最大长度重置为0。然后访问右子树，如果右子树存在，
 * 以当前节点作为左拐点，继续向左子树方向访问，
 * 即visit(root.right, 0, leftMax + 1)，
 * 右子树最大长度加1，左子树最大长度重置为0。
 *
 **/
public class 二叉树中的最长交错路径 {
    private int max = 0;

    public int longestZigZag(TreeNode root) {
        // 从根节点开始访问，初始的左右子树最大长度都为0
        visit(root, 0, 0);
        // 返回最长的zigzag路径长度
        return max;
    }

    private void visit(TreeNode root, int leftMax, int rightMax) {
        // 更新最大长度，取左右子树最大长度的较大值
        max = Math.max(max, Math.max(leftMax, rightMax));

        // 如果当前节点为空，结束访问
        if (root == null) {
            return;
        }

        // 访问左子树
        if (root.left != null) {
            // 在左子树中，以当前节点作为右拐点，继续向右子树方向访问，左子树最大长度加1，右子树最大长度重置为0
            visit(root.left, rightMax + 1, 0);
        }

        // 访问右子树
        if (root.right != null) {
            // 在右子树中，以当前节点作为左拐点，继续向左子树方向访问，右子树最大长度加1，左子树最大长度重置为0
            visit(root.right, 0, leftMax + 1);
        }
        /*
        * 上面为什么往左拐是rightMax + 1，右拐leftMax + 1？
        * 首先，往那边拐，对应的函数参数位置+1这个好理解
        * 现在讲解左拐是rightMax + 1，因为你现在是左拐了对吧
        * 然后题目是交叉长度，所以你左拐的长度就得是上一个的右拐的长度，
        * 也就是等同于当前rightMax ，再去+ 1
        * 右拐也同理
        * 每拐一次，也就是每执行一次visit函数，max赋值左大和右大之间的最大值
        * */
    }
}
